package com.bluesky.javawebbrowser.domain;

import java.util.ArrayList;
import java.util.List;

public class QuickSort {

	static void sort(int[] list, int start,int end){
		if(start>=end || end <=start)
			return;
		
		List<Integer> less = new ArrayList<Integer>();
		List<Integer> greater = new ArrayList<Integer>();
		
		int pivot = list[start];
		
		for(int i=start+1;i<=end;i++)
		{
			int d = list[i];
			if(d<pivot)
				less.add(d);
			else
				greater.add(d);
		}
		
		for(int i=0;i<less.size();i++)
			list[start+i]=less.get(i);
		
		list[start+less.size()]=pivot;
		
		for(int i=0;i<greater.size();i++)
			list[start+less.size()+1+i]=greater.get(i);
		
		sort(list,start,start+less.size());
		sort(list,start+less.size()+1,end);
	}
	
	public static void main(String[] args) {
		int[] list;
		list = new int[]{33344,1,2,8,9,10,3,4,5,6,7,100,9000,111,2,3234,234,2354,54,64,67};
		
		sort(list,0,list.length-1);
		
		for(int i=0;i<list.length;i++)
			System.out.print(list[i]+",");
	}
}
